
from typing import List

class Solution:
    def __init__(self) -> None:
        self.cnt = 0
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []

        def valid(A):
            flag = 0
            for e in A:
                if e =='(':
                    flag += 1
                else:
                    flag -=1
                if flag < 0 or flag > len(A)/2:
                    return False
                
            return flag == 0
        def generate(A):
            self.cnt += 1
            if len(A) == n*2:
                if valid(A):
                    ans.append(''.join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()

                A.append(')')
                generate(A)
                A.pop()
        generate([])
        print('time', self.cnt)
        return ans
    
    def generateParenthesis2(self, n: int) -> List[str]:
        self.ans = []

        def do(A):
            if len(A) == n*2:
                self.ans.append(''.join(A))
            elif len(A) < n*2:
                A = ['('] + A + [')']
                do(A)
                A = A[1:-1]

                A = A + ['(', ')']
                do(A)
                A = A[:-2]
        
        do([])
        return self.ans




if __name__ == "__main__":
    print("Given n pairs of parentheses, py: 真特么，连这个都想不出来了。。遇到问题先从暴力法简单点开始思考\n\n")

    r = Solution().generateParenthesis(3)
    print(r)
    print('method 2')
    r = Solution().generateParenthesis2(3)
    print(r)